package leetcode

import kotlinetc.println

//https://leetcode.com/problems/minimum-window-substring/

/**
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
 * 类似其他使用滑动窗口解法  [findMaxConsecutiveOnesIII]
 */
fun main(args: Array<String>) {

    println("acb".toSortedSet() == "abc".toSortedSet())


    //"bbaa" "aba"
    //ADOBECODEBANC  ABC
    //WADOBECODEBANC  W

    //"ask_not_what_your_country_can_do_for_you_ask_what_you_can_do_for_your_country"
    //"ask_country"

    //at_your_country_can_do_for_you_ask_what_you_can_do_for_your_country
    //ask_country

    //cabwefgewcwaefgcf
    //cae
    //cwae

    //"aaabbbbbcdd"  "abcdd"
    //该例不通过主要是忽略了在跳过第一个字母后，后面都不再能找到a，所以第三个a是不能跳过的
    //这里需要对每个字母进行计数，如果后面剩下的字母个数不比目标串中的字母个数多，那么left就不能继续右移了，此时只能右移right直到所有的目标字母被包含进来
    minWindow("cabwefgewcwaefgcf", "cae")
            .println()
    minwindowVersion1("aa", "aa").println()
    /////////////"01234567890123456789012345678"
}

/**
 * 会TLE，需要优化
 */
//TODO
fun minWindow(s: String, t: String): String {

    var bestLeft = 0
    var bestRight = -1
    var left = 0
    var right: Int
    var leftSet = false
    var i = 0
    val windowStr = StringBuffer()

    //记录每个字母个数
    val sTable = Array(128, { 0 })
    val tTable = Array(128, { 0 })

    t.forEach {
        tTable[it.toInt()]++
    }

    while (i < s.length) {
        val c = s[i]
        right = i
        if (c in t) {
            windowStr.append(c)
            //第一次确定left位置
            if (leftSet.not()) {
                leftSet = true
                left = i
            }
            if (windowStr.length >= t.length) {
                val hasContain = hasContain(windowStr.toString(), tTable)
                if (hasContain) {
                    if (right - left < bestRight - bestLeft || bestRight == -1) {
                        bestLeft = left
                        bestRight = right
                    }
                    //考虑到left左移之后，剩余的字符串仍然可以包含目标字符串 ，那么left可以左移到 包含目标字符串
                    //可以直接先移动一位
                    left++
                    windowStr.deleteCharAt(0)
                    while (left < s.length) {
                        if (s[left] in t) {
                            val contain = if (windowStr.length < t.length) false else hasContain(windowStr.toString(), tTable)
                            if (contain /*|| sTable[s[left].toInt()] > tTable[s[left].toInt()]*/) {

                                if (right - left < bestRight - bestLeft) {
                                    bestLeft = left
                                    bestRight = right
                                }

                                if (windowStr.isNotEmpty())
                                    windowStr.deleteCharAt(0)
                            } else {
                                break
                            }
                        }
                        left++
                    }
                    //可能left 越过right
                    if (left >= right) {
                        right = left
                        i = left
                    }
                }
            }


        }
        i++
    }
    println("$bestLeft $bestRight")
    return s.substring(bestLeft, bestRight + 1)
}


//Classic
fun minwindowVersion1(s: String, t: String): String {

    var curr = 0 //记录已经包含的字母个数
    val tTable = Array(128) { 0 }
    val currTable = Array(128) { 0 }

    var l = 0
    var r = 0

    var bestL = 0
    var bestR = -1
    t.forEach {
        tTable[it.toInt()]++
    }

    val length = s.length
    val tLen = t.length
    for (i in 0 until length) {
        val c = s[i]
        r = i
        if (l == -1) l = i
        val count = tTable[c.toInt()]

        currTable[c.toInt()]++
        if (currTable[c.toInt()] <= count)
            curr++


        //l 右移，直到窗口不能包含目标串，此过程中更新最小窗口边界
        while (l <= r && curr == tLen) {
            val index = s[l].toInt()

            //由于已经找到了包含所有字母的串，先直接更新最小窗口（如果存在的话）
            if (r - l < bestR - bestL || bestR == -1) {
                bestL = l
                bestR = r
            }

            //l 位置的字母计数减一
            currTable[index]--
            //如果l位置字母去除后 不再包含目标字母串，那么curr 计数减一，同时退出while循环
            if (tTable[index] != 0 && currTable[index] < tTable[index])
                curr--

            l++
        }
    }
    println("$bestL  $bestR")
    return s.substring(bestL, bestR + 1)
}

fun hasContain(toString: String, tTable: Array<Int>): Boolean {

    val sTable = Array(128, { 0 })
    toString.forEach {
        sTable[it.toInt()]++
    }

    tTable.forEachIndexed { index: Int, i: Int ->
        if (sTable[index] < i)
            return false
    }
    return true
}
